// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// binarySearch 在排序的整数“数组”中搜索给定的整数“针”
// 如果“针”存在于“数组”中，则返回 true，否则返回 false
func binarySearch(needle int, array []int) bool {
	// 将“array”的“low”和“high”索引分别设置为开头和结尾。
	low := 0
	high := len(array) - 1

	// 继续循环，直到“低”和“高”指标相互交叉
	for low <= high {
		// 计算中位数指数
		median := (low + high) / 2

		// 如果中值索引处的元素小于“针”，
		// 然后搜索“数组”的右半部分
		if array[median] < needle {
			low = median + 1
		} else {
			// 否则，搜索“数组”的左半部分。
			high = median - 1
		}
	}

	// 通过比较“低”索引处的元素来检查“数组”中是否存在“针”
	// 如果“低”等于“数组”的长度或“低”索引处的元素不等于“针”，
	// 则“针”不存在于“数组”中。
	if low == len(array) || array[low] != needle {
		return false
	}

	// 否则，“针”存在于“阵列”中
	return true
}

func main() {
	array := []int{1, 2, 9, 20, 31, 45, 63, 70, 100}
	fmt.Println(binarySearch(63, array))
}

//$ go run binarySearch.go
//true
